package com.qjc.demo.data_structure.stack;

import java.util.Stack;

/**
 * @Description: 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * <p>
 * 输入: "([)]"
 * 输出: false
 * </p>
 * <p>
 * 输入: "{[]}"
 * 输出: true
 * </p>
 * @Author: qjc
 * @Date: 2020/1/16
 */
public class BracketsSolution {

    public static void main(String[] args) {
        String bracketsString = "{[]}";
        boolean a = isValid(bracketsString);
        System.err.println(a);
    }

    /**
     * Stack这种数据结构用途很广泛，在计算机的使用中，大量的运用了栈，比如编译器中的词法分析器、Java虚拟机、软件中的撤销操作（Undo）、浏览器中的回退操作，编译器中的函数调用实现等等。
     *
     * @param bracketsString
     * @return
     */
    private static boolean isValid(String bracketsString) {
        Stack<Character> stack = new Stack<>();

        char[] chars = bracketsString.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char bracket = chars[i];
            if (bracket == '{' || bracket == '[' || bracket == '(') {
                //如果是左边括号则入栈
                stack.push(bracket);
            } else {
                //如果是右边括号则判断
                if (stack.size() == 0) {
                    return false;
                }
                Character character = stack.peek();//获取栈顶元素

                char match;
                if (bracket == '}') {
                    match = '{';
                } else if (bracket == ']') {
                    match = '[';
                } else {
                    match = '(';
                }
                if (character != match) {
                    return false;
                } else {
                    stack.pop();//如果匹配则弹出栈
                }
            }
        }
        if (stack.size() != 0) {
            //最终栈中元素不为空则说明不匹配
            return false;
        } else {
            return true;
        }
    }


}
